﻿// 0927train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 AI 识别到面板上有N（1 ≤N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠
 由于AI识别误差，每次识别到的指示灯位置可能有差异，以4个坐标值
 描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)请输出先行后列排序的指示灯的编号，
 排序规则：
1. 每次在尚未排序的灯中挑选最高的灯作为的基准灯
2. 找出和基准灯属于同一行所有的灯进行排序。
两个灯高低偏差不超过灯半径算同一行(即两个灯坐标的差灯高度的一半)。

输入描述
第一行为N，表示灯的个数
接下来N行，每行为1个灯的坐标信息，格式为：
编号 x1 y1 x2 y2
1：编号全局唯一
2：1<编号≤100
3：0≤x1 < x2≤1000
4：0≤y1 < y2 ≤ 1000

输出描述
排序后的编号列表，编号之间以空格分隔
示例1：
输入
5
1 0 0 2 2
2 6 1 8 3
3 3 2 5 4
5 5 4 7 6
4 0 4 2 6
输出
1 2 3 4 5

x1 y1 x2 y2
输出先行后列排序的指示灯的编号
先找出同一行的灯，两个灯高低偏差不超过灯半径算同一行
 */
class Solution01
{
public:
	struct Node
	{
		int index, x1, y1, x2, y2;
		Node() = default;
		Node(int index, int x1, int y1, int x2, int y2) :index(index), x1(x1), y1(y1), x2(x2), y2(y2) {};
	};

	Solution01(vector<vector<int>>&grid, int total)
	{
		vector<Node>node_vec;
		for (auto&item:grid)
		{
			node_vec.push_back(Node(item[0], item[1], item[2], item[3], item[4]));
		}

		sort(node_vec.begin(), node_vec.end(), [](Node&node_1,Node&node_2)
		{
				return node_1.y1 < node_2.y1;
		});


		Node base_node = node_vec[0];
		double base_diff = (base_node.y2 - base_node.y1) / 2;
		double base_pos = base_node.y1 + base_diff;

		int layer = 0;
		vector<vector<Node>>result;
		result.push_back({ base_node });
		unordered_set<int>check_set;
		check_set.insert(base_node.index);

		while (check_set.size()!=total)
		{
			int v_size = node_vec.size();
			for (int i=0; i< v_size; i++)
			{
				if (check_set.count(node_vec[i].index) > 0) continue;

				Node curr_node = node_vec[i];
				double curr_pos = curr_node.y1 + (curr_node.y2 - curr_node.y1) / 2;
				if (abs(curr_pos - base_pos)<=base_diff)
				{
					result[layer].push_back(curr_node);
					check_set.insert(curr_node.index);
				}
				//for
			}
			//扫出下一轮的base
			vector<Node>new_vec;
			for (auto&item:node_vec)
			{
				if (check_set.count(item.index)==0)
				{
					new_vec.push_back(item);
				}
			}
			//元素全部排完了，break
			if (new_vec.empty()) break;

			sort(new_vec.begin(), new_vec.end(), [](Node& node_1, Node& node_2)
				{
					return node_1.y1 < node_2.y1;
				});
			base_node = new_vec[0];
			base_diff = (base_node.y2 - base_node.y1) / 2;
			base_pos = base_node.y1 + base_diff;
			result.push_back({ base_node });
			check_set.insert(base_node.index);
			layer++;

			node_vec = new_vec;
			//while---
		}
		

		for (auto&item_v:result)
		{
			sort(item_v.begin(), item_v.end(), [](Node&node_1, Node&node_2)
				{
					return node_1.x1 < node_2.x1;
				});

			for (auto&node:item_v)
			{
				cout << node.index << ' ';
			}

		}

		//Solution01
	}
	//
};


/*
 你有 n 台机器编号为 1~n，每台都需要完成完成一项工作，机器经过配置后都能完成独立完成一项工作。
假设第 i 台机器你需要花 B 分钟进行设置，然后开始运行，J 分钟后完成任务。
现在，你需要选择布置工作的顺序，使得用最短的时间完成所有工作。
注意，不能同时对两台进行配置，但配置完成的机器们可以同时执行他们各自的工作。

输入描述：
第一行输入代表总共有 M 组任务数据（1<M<=10）。
每组数第一行为一个整数指定机器的数量 N（0<N<=1000）。
随后的 N 行每行两个整数，第一个表示 B（0<=B<=10000），第二个表示 J（0<=J<=10000）。
每组数据连续输入，不会用空行分隔。各组任务单独计时。

输出描述：
对于每组任务，输出最短完成时间，且每组的结果独占一行。例如，两组任务就应该有两行输出。

示例1 输入输出 示例仅供调试，后台判题数据一般不包含示例
输入
1
1
2 2
输出
4
解释：
第一行为一组任务，第二行1代表只有一台机器，第三行表示该机器配置需2分钟，执行需2分钟。

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
2
2
1 1
2 2
3
1 1
2 2
3 3
输出
4
7
解释：
第一行2代表两组任务，
第二行2代表第一组任务有2个机器，
第三行1 1代表机器1配置需要1分运行需要1分，
第四行2 2代表机器2配置需要2分运行需要2分，
第五行3代表第二组任务需要3个机器，
第六行-8行分别表示3个机器的配置与运行时间。
 */
class Solution02
{
public:
	int compute(vector<pair<int, int>>&pair_vec)
	{
		sort(pair_vec.begin(), pair_vec.end(), [](pair<int, int>& p_1, pair<int, int>& p_2)
			{
				return p_1.second > p_2.second;
			});

		int prev_cost = 0;
		vector<int>complete_vec;
		int v_size = pair_vec.size();
		for (int i=0; i<v_size; i++)
		{
			prev_cost += pair_vec[i].first;
			complete_vec.push_back(prev_cost + pair_vec[i].second);
			//for---
		}

		int result = *max_element(complete_vec.begin(), complete_vec.end());

		return result;
		//compute
	}

	Solution02(vector<vector<pair<int,int>>>&origin_vec)
	{
		//优先启动耗时最长的机器
		//所有配置时间全部加上，计算除了最后一台机器，运行时间是否超过配置时间
		vector<int>result;

		for (auto&item:origin_vec)
		{
			int res = compute(item);
			result.push_back(res);
			//for---
		}

		int result_size = result.size();
		for (int i=0; i<result_size; i++)
		{
			cout << result[i];
			if (i!=result_size-1)
			{
				cout << '\n';
			}
		}

		//Solution02
	}
};


int main()
{
	{
		int total_size;
		cin >> total_size;
		vector<vector<pair<int, int>>>origin_vec(total_size);

		for (int r=0; r<total_size; r++)
		{
			int v_size;
			cin >> v_size;
			vector<pair<int, int>>item_v(v_size);
			for (int c=0; c<v_size; c++)
			{
				pair<int, int>p_item;
				cin >> p_item.first >> p_item.second;
				item_v[c] = p_item;
			}
			origin_vec[r] = item_v;
		}

		Solution02 solu(origin_vec);
		return 0;
	}
	int row_size;
	cin >> row_size;
	int col_size = 5;
	vector<vector<int>>grid(row_size, vector<int>(col_size));
	for (int r=0; r< row_size; r++)
	{
		for (int c=0; c< col_size; c++)
		{
			cin >> grid[r][c];
		}
	}
	Solution01 solu(grid, row_size);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
